package org.br.plotter.parser.fft;

import java.util.*;

public final class FastFourierTransform {

    private int n, nu;

    private int bitrev(int j) {

        int j2;
        int j1 = j;
        int k = 0;
        for (int i = 1; i <= nu; i++) {
            j2 = j1/2;
            k  = 2*k + j1 - 2*j2;
            j1 = j2;
        }
        return k;
    }

    public final double[] fftMag(double[] x) {
        // assume n is a power of 2
        n = x.length;
        nu =  (int) (Math.log(n)/Math.log(2));
        int length = 2<<nu-1;
        if(length != x.length) {
        	double[] temp = new double[length];
        	System.arraycopy(x, 0, temp, 0,length);
        	x=temp;
        	n=length;
        }
        int n2 = n/2;
        int nu1 = nu - 1;
        double[] xre = new double[n];
        double[] xim = new double[n];
        double[] mag = new double[n2];
        double tr, ti, p, arg, c, s;
        for (int i = 0; i < n; i++) {
            xre[i] = x[i];
            xim[i] = 0.0f;
        }
        int k = 0;

        for (int l = 1; l <= nu; l++) {
            while (k < n) {
                for (int i = 1; i <= n2; i++) {
                    p = bitrev (k >> nu1);
                    arg = 2 *  Math.PI * p / n;
                    c =  Math.cos (arg);
                    s =  Math.sin (arg);
                    tr = xre[k+n2]*c + xim[k+n2]*s;
                    ti = xim[k+n2]*c - xre[k+n2]*s;
                    xre[k+n2] = xre[k] - tr;
                    xim[k+n2] = xim[k] - ti;
                    xre[k] += tr;
                    xim[k] += ti;
                    k++;
                }
                k += n2;
            }
            k = 0;
            nu1--;
            n2 = n2/2;
        }
        k = 0;
        int r;
        while (k < n) {
            r = bitrev (k);
            if (r > k) {
                tr = xre[k];
                ti = xim[k];
                xre[k] = xre[r];
                xim[k] = xim[r];
                xre[r] = tr;
                xim[r] = ti;
            }
            k++;
        }

        mag[0] = (Math.sqrt(xre[0]*xre[0] + xim[0]*xim[0]))/n;
        for (int i = 1; i < n/2; i++)
            mag[i]= 2 *  (Math.sqrt(xre[i]*xre[i] + xim[i]*xim[i]))/n;
        return mag;
    }
    
    public List<double[]> fft(List<double[]> data) {
    	double[] tofft  =fromList(data);
    	double[] fft = fftMag(tofft);
    	return fromFloatArray(fft,data);
    }
    
   private double[] fromList(List<double[]> data) {
	   int size= data.size();
	   double[] result = new double[size];
	   for(int i=0;i<size;i++) {
		   result[i] = data.get(i)[1];
	   }
	   return result;
   }
    
   private List<double[]> fromFloatArray(double[] d, List<double[]> base) {
	   List<double[]> result = new ArrayList<double[]>();
	   
	   for(int i=0;i<d.length;i++) {
		   double[] temp = base.get(d.length -i -1 );
		  double[] ds = new double[2];
		  ds[1]=d[i];
		  if(temp[0] == 0)
			  continue;
		  ds[0] =2*Math.PI/temp[0];
		  result.add(ds);
	   }
	   return result;
   }
    }


